#include<iostream>
using namespace std;
int tmp[200] = { 0 };
void merge(int arr[], int begin1, int begin2, int end)
{
	int begin = begin1;
	int end1 = begin2;
	int i = 0;
	while (begin1 < end1 && begin2 < end)
	{
		while (begin1 < end1 && begin2 < end && arr[begin1] <= arr[begin2])
			tmp[i++] = arr[begin1++];

		while (begin1 < end1 && begin2 < end && arr[begin1] >= arr[begin2])
			tmp[i++] = arr[begin2++];
	}
	while(begin1<end1)
		tmp[i++] = arr[begin1++];

	while (begin2 < end)
		tmp[i++] = arr[begin2++];

	memcpy(arr+begin, tmp, i * sizeof(int));
}
void bottommupsort(int arr[],int n)
{
	int i = 1;
	for (i; i < n; i++)
	{
		int t = i;
		int j = 0;
		for (j; j + 2*t < n; j+=2*t)
		{
			merge(arr, j, j + t, j + 2 * t);
		}
		if (j + t < n)
			merge(arr, j, j + i, n);
	}
}
int main()
{
	int arr[8] = { 9,4,5,2,1,7,4,6 };
	bottommupsort(arr, 8);
	for (auto i : arr)
	{
		cout << i << ' ';
	}
}